package 题目集.动态规划.最长公共子串;

import org.junit.Test;

/**
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 *
 * https://leetcode.cn/problems/longest-common-subsequence/description/
 */
public class 最长公共子序列 {
    /**
     * 假设已知了text1[0..i-1]和text2[0..j-1] 最长公共序列为 res。
     * 那么text1[0..i]和text2[0..j] 最长公共序列就只有一下几种情况：
     *  1. text1[i] 和 text2[j]都要
     *  2. 要text[i]不要text[j]
     *  3. 要text[j]不要text[i]
     *  4. text[i]和text[j]都不要
     */
    public int longestCommonSubsequence(String text1, String text2) {
        t1 = text1.toCharArray();
        t2 = text2.toCharArray();
//        dp = new Integer[text1.length() + 1][text2.length() + 1];
//        return dfs(text1.length() - 1, text2.length() - 1);
        return dpFun(text1.length(), text2.length());
    }

    Integer[][] dp;
    char[] t1;
    char[] t2;

    public int dfs(int i, int j) {
        if (i < 0 || j < 0) return 0;
        if (dp[i][j] != null) return dp[i][j];
        if (t1[i] == t2[j]) {
            dp[i][j] = dfs(i - 1, j - 1) + 1;
            return dp[i][j];
        }
        int p1 = dfs(i - 1, j);
        int p2 = dfs(i, j - 1);
        int no = dfs(i - 1, j - 1);
        int res = Math.max(no, Math.max(p1, p2));
        dp[i][j] = res;
        return dp[i][j];
    }

    public int dpFun(int n, int m) {
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (t1[i-1]==t2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
    @Test
    public void test() {
        System.out.println(longestCommonSubsequence("ABCDEABCD", "AABZ"));
    }
}
